# 97. 交错字符串
# 思路：s1字符串的前i个字符和s2字符串的前j个字符，是否能交错成s3的前(i+j)个字符
def isInterleave(s1: str, s2: str, s3: str) -> bool:
    # m 是行，n 是列
    m = len(s1)
    n = len(s2)

    s3_len = len(s3)
    if m + n != s3_len:
        return False

    dp = [[False for _ in range(n + 1)] for _ in range(m + 1)]
    dp[0][0] = True

    # 填满 0 列
    for column in range(1, m + 1):
        dp[column][0] = s1[column - 1] == s3[column - 1] and dp[column - 1][0]

    # 填满 0 行
    for row in range(1, n + 1):
        dp[0][row] = s2[row - 1] == s3[row - 1] and dp[0][row - 1]

    # s1 字符串的前 i 个字符
    for i in range(1, m + 1):
        # s2 字符串的前 j 个字符
        s_i = s1[i - 1]
        for j in range(1, n + 1):
            s_j = s2[j - 1]
            target = s3[i + j - 1]
            # 状态转移方程
            dp[i][j] = (dp[i - 1][j] and target == s_i) or (dp[i][j - 1] and target == s_j)
    return dp[m][n]


s1_1 = "aabcc"
s2_1 = "dbbca"
s3_1 = "aadbbcbcac"
result = isInterleave(s1_1, s2_1, s3_1)
print(f"result:{result}")

s1_1 = ""
s2_1 = ""
s3_1 = ""
result = isInterleave(s1_1, s2_1, s3_1)
print(f"result:{result}")

s1_1 = "db"
s2_1 = "b"
s3_1 = "cbb"
result = isInterleave(s1_1, s2_1, s3_1)
print(f"result:{result}")
